package com.suxin.algorithm.linked;

/**
 * @author Tang
 * @classname JosephRingLinked
 * @description [ 约思夫环问题:https://blog.csdn.net/weixin_42250302/article/details/104215326 ]
 * @date 2022/4/1 16:16
 */
public class JosephRingLinked {

    private Node head;
    private Node tail;

    public void createHead(Integer no, Integer key) {
        head = new Node(no, key, null);
        tail = head;
    }

    public void createTail(Integer no, Integer key) {
        Node node = new Node(no, key, head);
        tail.next = node;
        tail = node;
    }

    public String print() {
        StringBuilder sb = new StringBuilder();
        Node cur = this.head;
        while (cur != null && cur.next != head) {
            sb.append(cur.key).append("-->");
            cur = cur.next;
        }
        sb.append("NULL");
        return sb.toString();
    }

    public static class Node {
        /**
         * id
         */
        private Integer no;
        /**
         * 人的序号
         */
        private Integer key;
        private Node next;

        public Node(Integer no, Integer key, Node next) {
            this.no = no;
            this.key = key;
            this.next = next;
        }
    }

    public void josephRing(int[] v,int m) {
        this.createHead(1,v[0]);
        // 1.创建环
        for (int i = 1; i < v.length; i++) {
            this.createTail(i+1, v[i]);
        }
        // 2.报数，剔除
        Node temp = this.head;
        Node pre = temp;
        int i = 1;
        while (temp != null && temp.next != temp) {
            if (i % m == 0) {
                System.out.println("序号:--->" + temp.no + ",序号值:--->" + temp.key + ",出队");
                pre.next = temp.next;
                i = 0;
            }else {
                pre = temp;
            }
            temp = temp.next;
            i++;
        }
        System.out.println("序号:--->" + temp.no + "序号值:--->" + temp.key + "最后出队!");
    }

    public static void main(String[] args) {
        JosephRingLinked linked = new JosephRingLinked();
//        System.out.println("原始链表:" + linked.print());
        linked.josephRing(new int[]{3,5,7,8,9,1,10,12,34,21},3);
    }

}